package primary.primary0;

import java.util.HashMap;
import java.util.Map;

/**
 * 图, 并查集
 * 看看这个https://leetcode-cn.com/problems/couples-holding-hands/solution/liang-chong-100-de-jie-fa-bing-cha-ji-ta-26a6/
 */
public class S0765情侣牵手 {
    /**
     * 26, 单纯交换, 不知道为啥这样可行。
     * 这个序号大小没有关系, 就是单纯的编号
     * 最后凑成按照偶数序号成对的就可以了。就是不知道我看到一个不对的就换, 那么这种交换次数是不是最优解。
     */
    int count = 0;

    public int minSwapsCouples(int[] row) {
        Map<Integer, Integer> graph = new HashMap<>();
        for (int i = 0; i < row.length; i++) {
            // 存储一下每个人的位置
            graph.put(row[i], i);
        }
        int posiPare = -1;
        while (posiPare++ < row.length / 2 - 1) {
            if (Math.abs(row[posiPare * 2] - row[posiPare * 2 + 1]) == 1 && (row[posiPare * 2] + row[posiPare * 2 + 1]) % 4 == 1) {
                continue;
            }
            int otherOne = row[posiPare * 2] % 2 == 0 ? row[posiPare * 2] + 1 : row[posiPare * 2] - 1;
            swap(row, posiPare * 2 + 1, graph.get(otherOne), graph);
        }
        return count;
    }

    public void swap(int[] row, int start, int end, Map<Integer, Integer> graph) {
        count++;
        graph.put(row[start], end);
        graph.put(row[end], start);
        int temp = row[start];
        row[start] = row[end];
        row[end] = temp;
    }


    /**
     * 别人的并查集, 应该两两成对的, 但是却产生了环, 先求连通分量
     */
    public int minSwapsCouples2(int[] row) {
        int f = row[0];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 1; i < row.length; i++) {
            int n = row[i];
            while (map.containsKey(n)) {
                n = map.get(n);
            }
            if (i % 2 != 0 && n != (f ^ 1)) {
                map.put(f ^ 1, n);
            }
            f = n;
        }
        return map.size();
    }
}

/**
 * 官方解答, 并查集
 */
class Solution {
    public int minSwapsCouples(int[] row) {
        int n = row.length;
        int tot = n / 2; // 集合数量
        int[] f = new int[tot];
        for (int i = 0; i < tot; i++) {
            f[i] = i;
        }

        for (int i = 0; i < n; i += 2) {
            int l = row[i] / 2;
            int r = row[i + 1] / 2;
            add(f, l, r);
        }

        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < tot; i++) {
            int fx = getf(f, i);
            map.put(fx, map.getOrDefault(fx, 0) + 1);
        }

        int ret = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            ret += entry.getValue() - 1;
        }
        return ret;
    }

    public int getf(int[] f, int x) {
        if (f[x] == x) {
            return x;
        }
        int newf = getf(f, f[x]);
        f[x] = newf;
        return newf;
    }

    public void add(int[] f, int x, int y) {
        int fx = getf(f, x);
        int fy = getf(f, y);
        f[fx] = fy;
    }
}

